package com.lw.leetcode.dp.c;

import com.lw.test.util.Utils;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * c
 * dp
 * LCP 14. 切分数组
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/2 16:51
 */
public class SplitArray {

    public static void main(String[] args) {
        SplitArray test = new SplitArray();

        // 2
//        int[] arr = {2, 3, 3, 2, 3, 3};

        // 4
//        int[] arr = {2, 3, 5, 7};

        // 4
//        int[] arr = {91, 93, 74, 39, 85, 58, 32, 83, 12, 18};

        //
        int[] arr = Utils.getArr(100, 2, 1000000);

        int i = test.splitArray(arr);
        System.out.println(i);
    }

    public int splitArray(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] arr = new int[32];
        int last = 0;
        for (int num : nums) {
            int length = find(num, arr);
            int m = last;
            for (int i = 0; i < length; i++) {
                Integer value = map.get(arr[i]);
                if (value != null) {
                    m = Math.min(m, value);
                }
            }
            for (int i = 0; i < length; i++) {
                map.put(arr[i], Math.min(map.getOrDefault(arr[i], Integer.MAX_VALUE), last));
            }
            last = m + 1;
        }
        return last;
    }

    private int find(int num, int[] arr) {
        int v = (int) Math.pow(num, 0.5);
        int index = 0;
        int i = 2;
        while (i <= v) {
            if (num % i == 0) {
                if (index == 0 || arr[index - 1] != i) {
                    arr[index++] = i;
                }
                num /= i;
                if (num == 1) {
                    return index;
                }
            } else {
                i++;
            }
        }
        if (num > 1) {
            arr[index++] = num;
        }
        return index;
    }

}
